package com.maxPriorityQueue;

/**
 * @author 罗俊华
 * @date 2021/5/12 - 11:14 上午
 */
public class MaxPQ<Key extends Comparable<Key>> implements MaxPriorityQueue<Key> {

    protected Key[] array;

    protected int size = 0;

    public MaxPQ(Key[] array) {
        this.array = array;
    }

    protected MaxPQ() {
    }

    public MaxPQ(int arrayLength) {
        this.array = (Key[]) new Comparable[arrayLength];
    }

    @Override
    public synchronized void insert(Key key) {

        while (size + 1 >= array.length) {
            try {
                wait();
            } catch (InterruptedException e) {
                Thread.interrupted();
            }
        }
        ++size;
        array[size] = key;
        floatUp(size);
        notifyAll();
    }

    @Override
    public synchronized Key getMax() {

        return null;
    }

    @Override
    public synchronized Key delMax() {
        try {
            while (size <= 0 || array[1] == null) {
                wait();
            }

            Key result = array[1];
            exchange(1, size);
            array[size] = null;
            size--;
            sink(1);
            return result;
        } catch (InterruptedException e) {
            Thread.interrupted();
        } finally {
            notifyAll();
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public synchronized int size() {
        return size;
    }

    @Override
    public synchronized void exchange(int i, int j) {
        Key temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 只要这个元素比它的父元素大，那么这个元素就可以一直上浮，直到根元素
     *
     * @param k
     */
    @Override
    public synchronized void floatUp(int k) {

        while (k > 1 && this.less(k / 2, k)) {
            exchange(k, k / 2);
            k = k / 2;
        }

    }

    @Override
    public synchronized void sink(int k) {
        this.sink(k, this.size);
    }

    protected synchronized void sink(int k, int size) {

        while (2 * k < size) {
            int leftChild = 2 * k;
            int rightChild = 2 * k + 1;
//            堆中，array[2*k+1]不能保证比array[2*k]大
            int maxChildIndex = leftChild;
//            选择出当前子节点中，最大的那一个节点，暗含，如果要下沉且有两个节点的话，有只考虑下沉右节点
            if (size > rightChild && less(leftChild, rightChild)) {
                maxChildIndex = rightChild;
            }

            if (!less(k, maxChildIndex)) {
                break;
            }
//          当前节点比两个子节点中最大的哪一个节点要小（这是有序堆的定义），才能下沉
            exchange(k, maxChildIndex);
            k = maxChildIndex;

        }
    }

    @Override
    public synchronized boolean less(int i, int j) {
        return array[i].compareTo(array[j]) < 0;
    }
}
